Swap nodes in pairs

Time: O(N); Space: O(1); easy

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Input: head = {ListNode} 1->2->3->4->None

Output: {ListNode} 2->1->4->3->None

Example 2:

Input: head = {ListNode} 5->None

Output: {ListNode} 5->None

Challenge:

  • Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

[1]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, self.next)

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        current = dummy

        while current.next and current.next.next:

            next_one, next_two, next_three = current.next, current.next.next, current.next.next.next

            current.next = next_two
            next_two.next = next_one
            next_one.next = next_three
            current = next_one

        return dummy.next

[3]:

s = Solution1()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
res = s.swapPairs(head)

exp = [2,1,4,3]
tmp = res
for val in exp:
    assert tmp.val == val
    tmp = tmp.next